package SortMethod;

import java.util.Arrays;

//第一次重复归并排序
public class MergeSortFirst {

    private MergeSortFirst() {
    }

    public static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        //解决最基本的问题： 1、没有数组—— l > r
        //                 2、数组只有一个一个元素—— l = r
        //数组递归下去是否会遇到最基本问题——必要设计
        //最小问题：只有一个元素时如何排序
        if (l >= r)
            return;
        //将传进来的数组一分为二
        int mid = l + (r - l) / 2;
        //将传进来数组的左半边排序
        sort(arr, l, mid);
        //将传进来数组的右半边排序
        sort(arr, mid + 1, r);
        //将传进来数组的左右半边变合并边排序
        merge(arr, l, mid, r);
    }

    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r) {
        //创建一个临时数组，复制传进来的数组，从l位置开始，长度为r+1
        E[] temp = Arrays.copyOfRange(arr, l, r + 1);
        //开始进行合并有序的arr[l,mid]与有序的arr[mid+1,r]为“一个”有序的数组
        //l和r为数组固有索引，不能被处理，所以要找替代,并初始化为各自开头索引
        int i = l, j = mid + 1;
        //使l到r有序
        for (int k = l; k <= r; k++) {  //r为最后一个数，所以要被遍历到
            //先处理两种情况，分别是左半边都进入数组，右半边还有。另一种与之相反
            //遇到这种情况就让未排满的那一边直接进入数组中就好了
            if (i > mid && j <= r) { //左半边都进入数组，右半边还有,j<=r可以不写，但合逻辑
                arr[k] = temp[j-l];
                j++;
            } else if (i <= mid && j > r) { //与上面同理
                arr[k] = temp[i-l];
                i++;
            } else if (temp[i-l].compareTo(temp[j-l]) <= 0) {//如果左半边索引对应的数比右半边索引对应的数小，就让左半边索引对应的数进入数组中
                arr[k] = temp[i-l];
                i++;
            } else { //最后一种情况刚好和第三种情况相反
                arr[k] = temp[j-l];
                j++;
            }

            /**说说第一次重复递归函数所犯下的错
             * 他们都出自merge函数，也就是归并函数，核心函数。
             * 1、数组一分为二，要有两个索引，i指向左半边的开头l，j指向右半边的开头mid+1。但是我写成了j=r。
             * 也就是我很机械的抄代码，没理解到位，压根没意识到i，j是两半边索引，错了活该
             * 2、最常见的错误，在temp数组中的索引是不同的应该是temp[i-l]我直接写成了temp[i],运行程序一直提示越界
             * temp复制的时候开头的索引已经变成了l，假如数组大小为10，此时l为5，当i为6的时候就是temp[11]了，不越界才怪,因此要i-l
             */

        }
    }
}
